#include <iostream>
#include <stdlib.h>
#include <ctime>

using namespace std;

typedef struct NODE
{
    int data;
    struct NODE *next;
}NODE,*pNODE;

void main( )
{
    pNODE head=NULL,s,p,pre;
    int a[10],i;

    srand((unsigned int)time(0));
    for(i=0;i<10;i++) 
    {
       a[i]=rand()%50;
       cout<<i<<"  "<<a[i]<<endl;
    }

    for(i=0;i<10;i++)
    {
        s=(pNODE)malloc(sizeof(NODE));   //creat a new room

        s->data=a[i];
        s->next=NULL;

        if(head=NULL)
        {
            head=s;                //initialization of head;
        }

        else
        {
            p=head;
            pre=p;
            while((p!=NULL)&&(s->data<p->data))
            {
                pre=p;
                p=p->next;
            }

            if(p==head)
            {
                s->next=head;
                head=s;
            }
            else if(p==NULL)
            {
                p->next=s;
            }
            else
            {
                s->next=pre->next;
                pre->next=s;
            }
        }
    }

    cout<<"put the sort"<<endl;
    p=head;

    while(p!=NULL)
    {
        printf("%d \n", p->data);
        p=p->next;
    }

    system("pause");
}





